吴老师百花 CC 班【链表】作业题解
T1【链表】猴子选大王
题目链接
点我跳转题目
题目分析
这道题目是经典的 约瑟夫问题（Josephus Problem），可以用 循环链表 来模拟猴子围圈报数的过程。具体步骤如下：
1. 构建循环链表：每个猴子是一个节点，data 存储编号，next 指向下一个猴子，形成环。
2. 模拟报数过程：
* 从编号 1 的猴子开始报数。
* 每次数到 m 时，当前猴子出圈（删除该节点）。
* 继续从下一个猴子开始重新报数，直到只剩一只猴子。
3. 返回结果：最后剩下的猴子的编号就是大王的编号。
代码实现
T2【链表】删除相等数
题目链接
点我跳转题目
题目分析
这道题目要求我们使用链表来存储给定的整数，然后删除所有与指定值 m 相等的节点，最后输出剩余的元素。具体步骤如下：
1. 构建链表：将输入的 n 个整数依次插入到链表中。
2. 删除操作：遍历链表，删除所有 data 等于 m 的节点。
3. 输出结果：遍历链表，输出剩余的元素。
代码实现
T3【链表】序列问题
题目链接
点我跳转题目
题目分析
这道题目要求我们在链表中所有值为 m 的节点后面插入一个值为 q 的新节点。具体步骤如下：
1. 构建链表：将输入的 n 个整数依次插入到链表中。
2. 插入操作：遍历链表，在每一个 data 等于 m 的节点后面插入一个值为 q 的新节点。
3. 输出结果：遍历链表，输出插入后的序列。
详细注释
T4 模拟链表操作
题目链接
点我跳转题目
题目分析
这道题目要求我们首先构建一个初始链表，然后进行 m 次插入操作，每次将元素 b 插入到元素 a 的后面。由于题目保证元素不重复，我们可以直接通过遍历链表找到对应的节点进行操作。
详细注释
T5 基础链表插入
题目链接
点我跳转题目
题目分析
这道题目要求我们使用链表来存储初始的数字序列，然后在指定的数字 a 后面插入一个新的数字 b。由于题目保证数字不重复，我们可以直接遍历链表找到对应的节点进行操作。
详细注释
T6 约瑟夫问题2
题目链接
点我跳转题目
题目分析
这道题目是经典的 约瑟夫问题（Josephus Problem），要求模拟n个人围成一圈，每次数到m的人出列，直到只剩最后一个人。由于n可能很大（1e6），直接模拟会超时，需要使用数学方法优化。
详细注释
关键点说明
1. 数学递推：
* 当 n=1 时，结果显然是 0（只有一个人）
* 递推关系：f(n,m) = (f(n-1,m) + m) % n
* 时间复杂度 O(n)，可以处理 n=1e6 的情况
2. 优化思路：
* 避免使用链表模拟，直接计算最后幸存者的位置
* 递归实现简洁，但可以改为迭代防止栈溢出
3. 边界处理：
* 当 n=1 时直接返回 0
* 保证 m > 0 且 n > 0
示例解析
输入：
计算过程：
1. f(1,3)=0
2. f(2,3)=(f(1,3)+3)%2=1
3. f(3,3)=(f(2,3)+3)%3=1
4. f(4,3)=(f(3,3)+3)%4=0
5. f(5,3)=(f(4,3)+3)%5=3
6. f(6,3)=(f(5,3)+3)%6=0
7. f(7,3)=(f(6,3)+3)%7=3
8. f(8,3)=(f(7,3)+3)%8=6
输出：
迭代优化版本
这个版本避免了递归的栈开销，更适合处理大数据量。
T7 排队就餐
题目链接
点我跳转题目
题目分析
这道题目要求我们模拟食堂排队的过程，初始有n个人排队，其中有m个人离开队伍。我们需要计算在这些人离开后，小明在队伍中的新位置。
详细注释
关键点说明
1. 输入处理：
* 读取初始队伍和离开人员名单
* 读取小明的编号
2. 队伍更新：
* 创建新队伍，只保留没有离开的人
* 使用find函数检查人员是否在离开名单中
3. 位置查找：
* 遍历新队伍查找小明的编号
* 位置从1开始计数
4. 输出结果：
* 输出小明在新队伍中的位置
示例解析
输入：
执行过程：
1. 初始队伍：[1,3,2,5,4]
2. 离开的人：[1,4,5]
3. 新队伍：[3,2]
4. 小明编号2的位置：第2个
输出：
T8 站队
题目链接
点我跳转题目
题目分析
这道题目要求我们根据每个同学前面的人的编号，重建整个队伍的排队顺序。关键在于理解输入数据的含义，并通过建立"前驱-后继"关系来重建队伍顺序。
详细注释
关键点说明
1. 数据结构：
* front数组存储每个同学前面的人
* back数组存储每个同学后面的人
2. 建立关系：
* 遍历front数组，填充back数组
* 如果i号同学前面是j号，那么j号后面就是i号
3. 寻找队首：
* 队首的特征是前面没有人（front[i] == 0）
4. 输出顺序：
* 从队首开始，沿着back数组依次输出
示例解析
输入：
执行过程：
1. front数组：[0,3,1,0,5,2]
2. back数组：[3,2,5,1,4,0]
3. 队首是3（front[3]==0）
4. 输出顺序：3→1→2→5→4
输出：
优化思路
1. 可以合并两个循环，在读取输入时直接建立back关系
2. 使用更直观的变量名，如prev和next代替front和back
3. 添加输入有效性检查，确保数据合法
